import copy


class Solution:
    def count(self, board, i, j):
        m = len(board)
        n = len(board[0])
        cnt = 0
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)]
        for dx, dy in directions:
            x, y = i + dx, j + dy
            if 0 <= x < m and 0 <= y < n:
                if board[x][y]:
                    cnt += 1

        return cnt

    def solve(self, matrix):
        m = len(matrix)
        n = len(matrix[0])
        temp = copy.deepcopy(matrix)
        for i in range(m):
            for j in range(n):
                if matrix[i][j] and self.count(temp, i, j) < 2:
                    matrix[i][j] = 0
                elif matrix[i][j] and self.count(temp, i, j) in [2, 3]:
                    continue
                elif matrix[i][j] and self.count(temp, i, j) > 3:
                    matrix[i][j] = 0
                elif not matrix[i][j] and self.count(temp, i, j) == 3:
                    matrix[i][j] = 1

        return matrix


if __name__ == "__main__":
    s = Solution()
    matrix = [[0, 1, 0], [0, 0, 1], [1, 1, 1], [0, 0, 0]]
    matrix = s.solve(matrix)
    for i in range(len(matrix)):
        print(matrix[i])
